1. Technical Field
The invention relates to data processing systems and more particularly to a data caching scheme for use on data processing systems. The invention relates still more particularly to use of the caching scheme for management of a buffer for a network adaptor receiving and/or transmitting data packets for a node of a distributed data processing system.
2. Description of the Related Art
The passing of data in either direction between a network communications link and a network node is commonly done by buffering the data. Buffering avoids any need for rigid synchronization of the network communications link and the internal operations of the network node. A buffer may be implemented using memory or data storage registers, a disk drive, a delay line, or any one of a number of technologies. Use of a buffer allows for differences in the rate of flow of information or time of occurrence of events when transmitting information between the communications link and node.
The organization of data for transmission over a communications link has a number of consequences relating to efficient use of the communications link, management of transmission and receipt of the data, efficient use of memory upon receipt of the data, among other things. For example, data are commonly organized into packets in which control and data elements are switched and transmitted as a composite whole. The use of packets simplifies a number of issues concerning routing, primarily by allowing simplified referencing for the packets or frames. Some management functions for the packet may then be executed on references associated with the packets, e.g. pointers to storage locations for the packets.
As described in copending patent application Ser. No. 08/171,050, filed on Dec. 21, 1993, titled "System and Method for Management of a Communications Buffer", and assigned to the assignee as the present application, various first-in, first-out (FIFO) lists may be used to support operation of a communications buffer. The referenced application provides for segregating data packets by size class and passing the segregated packets to frames sized to handle all packets of a class. Available frames in a buffer for each class of packets are tracked in FIFO lists of pointers to the frames. Frames may then be passed from their own receive FIFO buffer into frames in an addressable buffer, where a pointer taken from a FIFO list of available pointers indicates the frame used. The pointer is in turn placed in a receive queue, or for outbound data, a transmit queue, both of which may be implemented in FIFO lists.
As network data transmission rates increase the number of packets requiring buffering at any given time tends to increase. In the above example, this requires larger FIFO lists for available pointers and used pointers. When constructing a very large scale integration (VLSI) chip set to support FIFO queues and queuing logic, it is difficult to achieve simultaneously, both low latency times and large queue sizes. Large queues point to lengthened response times or to the use of expensive high speed memory devices. This phenomenon particularly exhibits itself when the memory capacity required to implement the queues exceeds on-chip capacity, as occurs frequently in multimedia applications with concurrent time-dependent audio/video streams and consequent demands for large queues. Increasing on chip memory capacity though may be prohibitively expensive, while limiting queue length may be untenable.
In a software implementation this problem manifests itself when queuing data is flushed from the processor cache, or a virtual storage page is swapped to a backing store. A very large processor cache might be required or the memory for the queue might be pinned to main storage to avoid a page fault. Either solution depends on probabilistic access times to be the best case all of the time, which is unlikely to occur.